洛谷题解 CF1716B 【Permutation Chain】

发表于 | 阅读次数：
本文字数： 4.6k | 阅读时长 ≈ 4 分钟

题意翻译

现在有一个长度为 $n$ 的数组 ${1,2,3,4,…,n}$ ，你每次操作可以交换其中任意两个数字的位置，但是要确保除了第一次交换是有两个数字不在原来的位置上外，后续每次操作之后只能增加一个不在原来位置上的数字（其实对应的就是题目中的 longest permutation chain ）

当所有数字都不在原来的位置时，操作结束

解题过程

首先根据题意，显然本题除了每组询问的 $chain$ 长度唯一外，操作过程并不唯一

题目其实就是要求我们构造一种操作使得符合上述题意

我这里采用的是先交换首位两个数字，再按照右左右左的顺序依次交换相邻两个数（因为第三组样例是）

貌似语言不好说明，那就举个例

$n$ 为奇数的例子

当 $n=5$ 时：

原始数组： $[1,2,3,4,5] \ \operatorname{fixedness}=5$

操作1： $[5,2,3,4,1] \ \operatorname{fixedness}=3$

操作2： $[5,2,3,1,4] \ \operatorname{fixedness}=2$

操作3： $[2,5,3,1,4] \ \operatorname{fixedness}=1$

操作4： $[2,5,1,3,4] \ \operatorname{fixedness}=0$

因此链长为 $5$

$n$ 为偶数的例子

$n=4$ 时：

原始数组： $[1,2,3,4] \ \operatorname{fixedness}=4$

操作1： $[4,2,3,1] \ \operatorname{fixedness}=2$

操作2： $[4,2,1,3] \ \operatorname{fixedness}=1$

操作3： $[2,4,1,3] \ \operatorname{fixedness}=0$

因此链长为 $4$

注意

不要漏了输出原始数组！

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<cstdio>
using namespace std;

int n,m,t,num[110],l,r; //l,r分别是目前左右操作的位置
bool pd=false;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        l=1;
        scanf("%d",&n);
        r=n;
        pd=false;
        printf("%d\n",n);
        for(int a=1;a<=n;++a)
        {
            num[a]=a;
            printf("%d ",num[a]);
        }
        printf("\n");
        if(n%2==0) //n为偶数时
        {
            while(l!=n/2+1||r!=n/2)
            {
                if(l==1&&r==n) //第一步
                {
                    int tmp=num[l];
                    num[l]=num[r];
                    num[r]=tmp;
                    for(int a=1;a<=n;++a)
                    {
                        printf("%d ",num[a]);
                    }
                    printf("\n");
                    l++;
                    r--;
                    continue;
                }
                else
                {
                    if(pd) //左边交换
                    {
                        pd=false;
                        int tmp=num[l];
                        num[l]=num[l-1];
                        num[l-1]=tmp;
                        for(int a=1;a<=n;++a)
                        {
                            printf("%d ",num[a]);
                        }
                        printf("\n");
                        l++;
                    }
                    else //右边交换
                    {
                        pd=true;
                        int tmp=num[r];
                        num[r]=num[r+1];
                        num[r+1]=tmp;
                        for(int a=1;a<=n;++a)
                        {
                            printf("%d ",num[a]);
                        }
                        printf("\n");
                        r--;
                    }
                }
            } 
        }
        else //n为奇数时
        {
            while(r!=(n+1)/2-1)
            {
                if(l==1&&r==n) //第一步
                {
                    int tmp=num[l];
                    num[l]=num[r];
                    num[r]=tmp;
                    for(int a=1;a<=n;++a)
                    {
                        printf("%d ",num[a]);
                    }
                    printf("\n");
                    l++;
                    r--;
                    continue;
                }
                else
                {
                    if(pd) //左边交换
                    {
                        pd=false;
                        int tmp=num[l];
                        num[l]=num[l-1];
                        num[l-1]=tmp;
                        for(int a=1;a<=n;++a)
                        {
                            printf("%d ",num[a]);
                        }
                        printf("\n");
                        l++;
                    }
                    else //右边交换
                    {
                        pd=true;
                        int tmp=num[r];
                        num[r]=num[r+1];
                        num[r+1]=tmp;
                        for(int a=1;a<=n;++a)
                        {
                            printf("%d ",num[a]);
                        }
                        printf("\n");
                        r--;
                    }
                }
            }
        }
    }
    return 0;
}

题目详见:https://www.luogu.com.cn/problem/show?pid=CF1716B